{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 对数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 简介"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对数是高等数学非常重要的概念，人类直到 17 世纪初才发明对数。 恩格斯曾经把对数、解析几何、微积分三大发明称为 17 世纪数学的三大成就。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 定义"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对数是[指数运算](https://math.haozi.me/pow.html)的逆运算。即假设有 $a^x = y(a > 0, a \\neq 1)$，则 x 称作以 a 为底的 y 的对数，记作 $x = \\log_a{y}$\n",
    "\n",
    "* 以 10 为底的对数，可以简写成 $\\lg^x$\n",
    "* 以 e 为底的对数，可以简写成 $\\ln^x$\n",
    "* 以 2 为底的对数，可以简写成 $lb^x$，在二分查找里会用到\n",
    "\n",
    "注意：在 Python 和 JS 里，log 函数默认是以 e 为底的：如 JS 里 `Math.log(Math.E) === 1`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 运算法则"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "名称 | 公式|证明(TODO)\n",
    "---|---|---\n",
    "和差公式 | $\\log_aMN=\\log _{a}\\!M+\\log_{a}\\!N$ | \n",
    "换底公式 | $\\log_a{x} = \\frac{\\log_bx}{\\log_ba}$ |\n",
    "次方公式 | $\\log_{a^n}{x^m} = \\frac{m}{n}\\log_ax$ |\n",
    "还原| $a^{\\log_ax} = x = \\log_a{a^x}$ |\n",
    "互换 | $M^{\\log_aN} = N^{\\log_aM}$ |\n",
    "倒数 | $\\log_ab = \\frac{1}{\\log_ba}$ |\n",
    "链式 | $\\log_ab \\cdot \\log_bc = \\log_ac$ |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这些公式在学校学习的时候很重要，是很多题的解题技巧，善用对数，可以避免天文数字的计算，将乘法运算变为加法运算。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## JS 实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "计算机里使用一些级数公式来计算对数，\n",
    "\n",
    "${\\displaystyle \\ln z=\\sum _{n=1}^{\\infty }{\\frac {-{(-1)}^{n}}{n}}(z-1)^{n}}$\n",
    "\n",
    "${\\displaystyle \\ln z=2\\sum _{n=0}^{\\infty }{\\frac {1}{2n+1}}\\left({\\frac {z-1}{z+1}}\\right)^{2n+1}}$\n",
    "\n",
    "参照之前求 [$\\pi$](https://math.haozi.me/PI.html) 和 [$e$](https://math.haozi.me/E.html) 的实现，大家可以自己尝试编程实现，然后可以对比一下两个公式的效率，在文章下面回复留言。\n",
    "\n",
    "如果这两个公式都来源于高等数学，如果你不知道这两个公式的推导步骤，即使编程求出结果，也仍然只是工程上的事，今天我主要想讲一个比较直观暴力的方法，但至少能够理解原理。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 暴力求对数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们知道对数是指数运算的逆运算，我们可以暴力地用二分法试出来。通过上面的换底公式，我们可以选定一个底。事实上，选择合适的底能降低计算量，为了便于演示，我们就以 10 为底，实现 js 中的 Math.log10 方法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以 $\\lg {1000}$ 为例，很容易知道，这个数不能大于结果 1000。上次我们已经实现了[指数运算](https://math.haozi.me/pow.html)，以及[绝对值](https://math.haozi.me/abs.html)，我们用二分查找试算：\n",
    "\n",
    "```\n",
    "10 ** 1000 过大\n",
    "10 ** 500 过大\n",
    "10 ** 250 过大\n",
    "10 ** 125 过大\n",
    "10 ** 62.5 过大\n",
    "10 ** 31.25 过大\n",
    "10 ** 15.625 过大\n",
    "10 ** 7.8125 过大\n",
    "10 ** 3.90625 过大\n",
    "10 ** 1.953125 小了\n",
    "   10 ** (1.953125 + (3.90625 - 1.953125) / 2)\n",
    "   ...\n",
    "```\n",
    "然后是编程实现它，我们要找到所有退出条件：\n",
    "\n",
    "* 如果 n == 0，由于没有任何数的次方等于 0（0的0次方数学上没有定义）。我们遵循 IEEE754 的规定返回 -Infinity\n",
    "* 如果 n = 1，直接返回 0\n",
    "* 幂方结果正好等于 n, 找到了，退出\n",
    "* 工程上，我们知道 js 浮点数精度问题，允许小于一定误差，认为两值相等，避免死循环\n",
    "\n",
    "### 实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```javascript\n",
    "const log10 = (n) => {\n",
    "  if (n < 0) return NaN\n",
    "  if (n === 0) return -Infinity\n",
    "  if (n === 1) return 0\n",
    "\n",
    "  let ret = n\n",
    "  let pre = NaN\n",
    "  while(true) {\n",
    "    const pow = 10 ** ret\n",
    "    if (pow > n) {\n",
    "      pre = ret\n",
    "      ret /=2\n",
    "    }\n",
    "\n",
    "    if (pow === n) break\n",
    "\n",
    "    if (pow < n) {\n",
    "      ret += (pre - ret) / 2\n",
    "    }\n",
    "    // 防御\n",
    "    if (Math.abs(pre - ret) < 1e-15) break\n",
    "  }\n",
    "  return ret\n",
    "}\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
